package tul.cot.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import tul.cot.MigrationTree;


public class TreeComparator implements Comparator<MigrationTree> {

	public static final Comparator<MigrationTree> instance = new TreeComparator();
	
	@Override
	public int compare(MigrationTree t1, MigrationTree t2) {
		String t1Str = getSortedTreeString(t1, true);
		String t2Str = getSortedTreeString(t2, true);
		
		return t1Str.compareTo(t2Str);
	}

	public static String getSortedTreeString(MigrationTree tree, boolean isRoot) {
		List<String> sonsStr = new ArrayList<String>();
		for (MigrationTree son: tree.getSons()) {
			sonsStr.add(getSortedTreeString(son, false));
		}
		
		Collections.sort(sonsStr);
		
		StringBuilder sb = new StringBuilder();
		if (sonsStr.size() > 0) {
			sb.append("(");
			sb.append(sonsStr.get(0));
			for (int i=1; i<sonsStr.size(); ++i) {
				sb.append(",");
				sb.append(sonsStr.get(i));
			}
			sb.append(")");
		}
		
		sb.append(tree.getLabel());
		if (isRoot) {
			sb.append(";");
		} else {
			sb.append(MigrationTree.NAME_LENGTH_SEP);
			sb.append(tree.getLength());
		}
		
		return sb.toString();
	}
}
